package com.leetcode.程序员面试金典.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;

/**
 * @author 覃国强
 * @date 2021-04-07 12:47
 */
public class 面试题_17_07_婴儿名字 {


  public static void main02(String[] args) {
    String[] outNames = {"Prf(48)", "Zvzm(31)", "Bbcpth(256)", "Jmqqsj(19)", "Uwy(26)",
        "Jylbla(100)", "Xioal(11)", "Npbu(62)", "Jpftyg(96)", "Alqw(702)", "Kxjw(36)", "Clplqf(8)",
        "Fayxe(155)", "Slfwyo(82)", "Xbesji(70)", "Oip(13)", "Fzoe(130)", "Sqwejn(19)",
        "Gsiiyo(215)", "Bcs(262)", "Icsvku(1)", "Vaakt(21)", "Axaqkm(100)", "Gaoo(98)", "Ghlj(35)",
        "Umt(13)", "Rqa(117)", "Zhc(44)", "Slh(66)", "Orpqim(69)", "Gql(67)", "Sfjdjc(62)",
        "Ccqunq(186)", "Oyo(32)", "Bvnkk(52)", "Pxzfjg(91)", "Kaaht(28)", "Vqnjg(142)", "Fshi(62)",
        "Phlto(41)", "Lnow(157)", "Mqgga(31)", "Adlue(171)", "Dma(170)", "Jnij(75)", "Ghk(14)",
        "Mrqlne(39)", "Rmlbnj(98)", "Aasipa(262)", "Wzt(41)", "Xuzubb(90)", "Kmrev(31)",
        "Iggrg(99)", "Lwyfn(50)", "Qlvglt(36)", "Jxv(152)", "Ttj(28)", "Ndc(62)", "Bjfkzo(54)"};
    String[] expectNames = {"Gsiiyo(215)", "Adlue(171)", "Iggrg(99)", "Umt(13)", "Bbcpth(256)",
        "Jxv(152)", "Vqnjg(142)", "Bvnkk(52)", "Bcs(262)", "Alqw(424)", "Kmrev(31)", "Bjfkzo(54)",
        "Oip(13)", "Qlvglt(36)", "Clplqf(8)", "Aasipa(262)", "Sfjdjc(62)", "Ccqunq(186)", "Oyo(32)",
        "Zhc(44)", "Fayxe(155)", "Ndc(62)", "Wzt(41)", "Xioal(11)", "Mqgga(31)", "Jpftyg(96)",
        "Fshi(62)", "Lnow(157)", "Rmlbnj(98)", "Ghk(14)", "Jylbla(100)", "Fzoe(130)", "Orpqim(69)",
        "Jnij(75)", "Jmqqsj(19)", "Kaaht(28)", "Ttj(28)", "Xuzubb(90)", "Dma(170)", "Slfwyo(82)",
        "Gaoo(98)", "Lwyfn(50)", "Pxzfjg(91)", "Gql(67)", "Sqwejn(19)", "Xbesji(70)", "Mrqlne(39)",
        "Ghlj(35)", "Rqa(117)", "Uwy(26)", "Prf(48)", "Axaqkm(100)", "Npbu(62)", "Kxjw(36)",
        "Zvzm(31)", "Icsvku(1)", "Phlto(41)", "Vaakt(21)", "Slh(66)"};

    System.out.println(outNames.length);
    System.out.println(expectNames.length);

    Solution solution = new Solution();
    solution.generateNames(outNames);
    solution.generateNames(expectNames);

  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    String[] names = {"Pwsuo(71)", "Prf(48)", "Rgbu(49)", "Zvzm(31)", "Xxcl(25)", "Bbcpth(42)",
        "Padz(70)", "Jmqqsj(19)", "Uwy(26)", "Jylbla(65)", "Xioal(11)", "Npbu(62)", "Jpftyg(96)",
        "Tal(46)", "Hnc(100)", "Yldu(85)", "Alqw(45)", "Wbcxi(34)", "Kxjw(36)", "Clplqf(8)",
        "Fayxe(66)", "Slfwyo(48)", "Xbesji(70)", "Pmbz(22)", "Oip(2)", "Fzoe(63)", "Qync(79)",
        "Utc(11)", "Sqwejn(19)", "Ngi(8)", "Gsiiyo(60)", "Bcs(73)", "Icsvku(1)", "Yzwm(92)",
        "Vaakt(21)", "Uvt(70)", "Axaqkm(100)", "Gyhh(84)", "Gaoo(98)", "Ghlj(35)", "Umt(13)",
        "Nfimij(52)", "Zmeop(77)", "Vje(29)", "Rqa(47)", "Upn(89)", "Zhc(44)", "Slh(66)",
        "Orpqim(69)", "Vxs(85)", "Gql(19)", "Sfjdjc(62)", "Ccqunq(93)", "Oyo(32)", "Bvnkk(52)",
        "Pxzfjg(45)", "Kaaht(28)", "Arrugl(57)", "Vqnjg(50)", "Dbufek(63)", "Fshi(62)", "Lvaaz(63)",
        "Phlto(41)", "Lnow(70)", "Mqgga(31)", "Adlue(82)", "Zqiqe(27)", "Mgs(46)", "Zboes(56)",
        "Dma(70)", "Jnij(57)", "Ghk(14)", "Mrqlne(39)", "Ljkzhs(35)", "Rmlbnj(42)", "Qszsny(93)",
        "Aasipa(26)", "Wzt(41)", "Xuzubb(90)", "Maeb(56)", "Mlo(18)", "Rttg(4)", "Kmrev(31)",
        "Kqjl(39)", "Iggrg(47)", "Mork(88)", "Lwyfn(50)", "Lcp(42)", "Zpm(5)", "Qlvglt(36)",
        "Liyd(48)", "Jxv(67)", "Xaq(70)", "Tkbn(81)", "Rgd(85)", "Ttj(28)", "Ndc(62)", "Bjfkzo(54)",
        "Lqrmqh(50)", "Vhdmab(41)"};
    String[] synonyms = {"(Uvt,Rqa)", "(Qync,Kqjl)", "(Fayxe,Upn)", "(Maeb,Xaq)", "(Pmbz,Vje)",
        "(Hnc,Dma)", "(Pwsuo,Gyhh)", "(Gyhh,Aasipa)", "(Fzoe,Lcp)", "(Mgs,Vhdmab)", "(Qync,Rgd)",
        "(Gql,Liyd)", "(Gyhh,Tkbn)", "(Arrugl,Adlue)", "(Wbcxi,Slfwyo)", "(Yzwm,Vqnjg)",
        "(Lnow,Vhdmab)", "(Lvaaz,Rttg)", "(Nfimij,Iggrg)", "(Vje,Lqrmqh)", "(Jylbla,Ljkzhs)",
        "(Jnij,Mlo)", "(Adlue,Zqiqe)", "(Qync,Rttg)", "(Gsiiyo,Vxs)", "(Xxcl,Fzoe)", "(Dbufek,Xaq)",
        "(Ccqunq,Qszsny)", "(Zmeop,Mork)", "(Qync,Ngi)", "(Zboes,Rmlbnj)", "(Yldu,Jxv)",
        "(Padz,Gsiiyo)", "(Oip,Utc)", "(Tal,Pxzfjg)", "(Adlue,Zpm)", "(Bbcpth,Mork)",
        "(Qync,Lvaaz)", "(Pmbz,Qync)", "(Alqw,Ngi)", "(Bcs,Maeb)", "(Rgbu,Zmeop)"};
    String[] popular = solution.trulyMostPopular(names, synonyms);
    System.out.println(Arrays.toString(popular));
  }


  static
  class Solution {

    public String[] trulyMostPopular(String[] names, String[] synonyms) {
      if (names == null || names.length == 0) {
        return new String[0];
      }

      List<Name> nameList = new ArrayList<>();
      Map<Name, Name> parentNameMap = new HashMap<>(names.length * 3 / 2);
      for (String nameStr : names) {
        Name name = generateName(nameStr);
        parentNameMap.put(name, name);
        nameList.add(name);
      }

      for (String synonym : synonyms) {
        Name[] peers = generatePeers(synonym);
        Name peer0RootParentName = getRootParentName(peers[0], parentNameMap);
        Name peer1RootParentName = getRootParentName(peers[1], parentNameMap);

        int compare = peer0RootParentName.compareTo(peer1RootParentName);

        if (compare < 0) {
          peer0RootParentName.rate += peer1RootParentName.rate;
          parentNameMap.put(peer1RootParentName, peer0RootParentName);
          parentNameMap.put(peer0RootParentName, peer0RootParentName);
        } else if (compare > 0) {
          peer1RootParentName.rate += peer0RootParentName.rate;
          parentNameMap.put(peer0RootParentName, peer1RootParentName);
          parentNameMap.put(peer1RootParentName, peer1RootParentName);
        }
      }

      List<Name> resultList = new ArrayList<>();
      for (Name name : nameList) {
        Name parentName = parentNameMap.get(name);
        if (name.equals(parentName)) {
          resultList.add(name);
        }
      }

      String[] result = new String[resultList.size()];
      int index = 0;
      for (Name name : resultList) {
        result[index++] = name.toString();
      }
      return result;
    }

    private Name getRootParentName(Name name, Map<Name, Name> parentNameMap) {
      while (parentNameMap.containsKey(name) && !parentNameMap.get(name).equals(name)) {
        name = parentNameMap.get(name);
      }
      if (parentNameMap.containsKey(name)) {
        return parentNameMap.get(name);
      }
      return name;
    }

    private Name[] generatePeers(String synonym) {
      String[] split = synonym.split(",");
      return new Name[]{
          new Name(split[0].substring(1)),
          new Name(split[1].substring(0, split[1].length() - 1))
      };
    }

    private Name generateName(String nameStr) {
      int index = nameStr.indexOf('(');
      String name = nameStr.substring(0, index);
      String rateStr = nameStr.substring(index + 1, nameStr.length() - 1);
      return new Name(name, Integer.parseInt(rateStr));
    }

    static class Name implements Comparable<Name> {

      String value;

      int rate;

      public Name(String value) {
        this.value = value;
      }

      public Name(String value, int rate) {
        this.value = value;
        this.rate = rate;
      }

      @Override
      public boolean equals(Object o) {
        if (this == o) {
          return true;
        }
        if (o == null || getClass() != o.getClass()) {
          return false;
        }
        Name name = (Name) o;
        return Objects.equals(value, name.value);
      }

      @Override
      public int hashCode() {
        return Objects.hash(value);
      }

      @Override
      public int compareTo(Name o) {
        return value.compareTo(o.value);
      }

      @Override
      public String toString() {
        return value + "(" + rate + ")";
      }
    }

    public void generateNames(String[] names) {
      Set<Name> nameSet = new TreeSet<>();
      for (String nameStr : names) {
        Name name = generateName(nameStr);
        nameSet.add(name);
      }
      System.out.println(nameSet);
    }
  }

}
